import javafx.scene.control.cell.PropertyValueFactory;

import javax.management.relation.RelationNotification;
import java.lang.annotation.ElementType;
import java.util.ArrayList;
import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-09-13
 * Time: 22:43
 */

public class Solution {
    private int[][] rects;
    private Random random;

    private int[] indexs;


    public Solution(int[][] rects) {
        this.rects = rects;
        this.random = new Random();
        int len = rects.length;
        this.indexs = new int[len+1];
        indexs[0] = 0;
        // 记录每块的坐标个数, 对所有的坐标进行重新编号, 然后使用前缀和
        int sum = 0;
        for (int i = 0; i < len; i++) {
            // 这个矩形包含的坐标的个数
            int count = (rects[i][2]-rects[i][0]+1) * (rects[i][3]-rects[i][1]+1);
            sum += count;
            indexs[i+1] = sum;
        }
    }


    /**
     *  二分查找, 返回随机数所属的 块
     */
    private int binarySearch(int rand, int[] indexs) {
        int len = indexs.length;
        int left = 1;
        int right = len-1;
        while (left < right) {
            int mid = ((right-left)>>1) + left;
            if (indexs[mid] < rand) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    public int[] pick() {
        int len = indexs.length;
        // 坐标的个数
        int total = indexs[len-1];
        int rand = random.nextInt(total) + 1;
        // 注意返回的是数组的下标 (也就是所属的块)
        int block = binarySearch(rand, indexs);
        // 根据块中编号的排列找出 随机数到底指的是哪个坐标
        int row = rects[block-1][3]-rects[block-1][1] + 1;
        int col = rects[block-1][2]-rects[block-1][0] + 1;
        int seq = rand - indexs[block-1];
        int x = rects[block-1][0] + ((seq-1)%col);
        int y = rects[block-1][1] + ((seq-1)/col);
        return new int[]{x, y};
    }
}

